Trong màu áo 1. FC Kaiserslautern, Klose ngày càng được chú ý vì khả năng ghi bàn của mình. Tháng 1 năm 2001, huấn luyện viên trưởng đội tuyển bóng đá quốc gia Ba Lan lúc đó là Jerzy Engel đã đến Đức để thuyết phục anh chơi cho Ba Lan. Nhưng Klose đã từ chối và nói anh quyết định sẽ thi đấu cho đội tuyển bóng đá quốc gia Đức. Ngày 24 tháng 3 năm 2001, anh thi đấu trận đầu tiên cho đội tuyển Đức dưới thời huấn luyện viên Rudi Völler trong trận gặp Albania.[19] Anh vào sân từ băng ghế dự bị và ghi bàn thắng ấn định tỉ số 2-1 cho Đức từ pha đánh đầu ở cự li gần.[20]

World Cup 2002

Tại World Cup 2002 tổ chức tại Hàn Quốc và Nhật Bản, Klose đã có 5 bàn thắng và tất cả đều từ những pha dứt điểm bằng đầu và đều diễn ra ở vòng đấu bảng. Trận đầu tiên anh lập hat-trick trong chiến thắng 8-0 của Đức trước Ả Rập Saudi.[21] Tiếp theo là bàn thắng trong trận hoà Cộng hòa Ireland 1-1[22] và cuối cùng là trong chiến thắng 2-0 trước Cameroon. Tại giải này, Đức đã lọt vào đến trận chung kết và thua Brasil 2-0, giành ngôi á quân thế giới.

World Cup 2006

World Cup 2006 tổ chức tại Đức lại một lần nữa chứng kiến sự toả sáng của Klose. Trong trận khai mạc gặp Costa Rica vào ngày 9 tháng 6 cũng là sinh nhật lần thứ 28 của mình, Klose đã lần lượt ghi hai bàn thắng ở phút 17 và 61 mang về chiến thắng 4-2 cho người Đức để được bầu chọn là Cầu thủ xuất sắc nhất trận đấu.[23] Rồi trong trận cuối cùng của vòng bảng gặp Ecuador vào ngày 20 tháng 6, anh tiếp tục ghi thêm hai bàn thắng nữa.

Tại vòng đấu loại trực tiếp, anh không ghi bàn trong chiến thắng 2-0 trước Thụy Điển nhưng vẫn được bầu chọn là Cầu thủ xuất sắc nhất trận đấu.[24] Tại trận tứ kết gặp Argentina, anh ghi bàn thắng vô cùng quan trọng ở phút 81 khi Đức đang bị dẫn trước 1-0. Sau đó Đức giành thắng lợi 4-2 trong loạt sút luân lưu để vào bán kết và dừng bước trước đội tuyển Ý với tỉ số 2-0. Chung cuộc người Đức giành hạng ba sau thắng lợi trước Bồ Đào Nha và Klose trở thành cầu thủ Đức thứ hai sau Gerd Müller đoạt danh hiệu vua phá lưới World Cup hay Chiếc giày vàng.[25] Anh còn cùng đồng đội Michael Ballack được bầu chọn vào đội hình tiêu biểu của World Cup.

Ngày 6 tháng 9 năm 2006, Klose ghi hai bàn trong chiến thắng 13-0 của Đức trước San Marino tại vòng loại Euro 2008. Hai bàn thắng này đưa tổng số bàn thắng của anh cho đội tuyển lên con số 33, bằng với cựu danh thủ Fritz Walter và giúp anh xếp hạng 7 trong số những tay săn bàn hàng đầu của bóng đá Đức. Ngày 8 tháng 9 năm 2007, Klose lần đầu tiên mang băng đội trưởng đội tuyển Đức trong trận gặp Wales và anh ghi cả hai bàn trong trận đấu đó, giúp Đức thắng 2-0.

Euro 2008

Klose tiếp tục có tên trong 23 cầu thủ Đức tham dự Euro 2008 của huấn luyện viên Joachim Löw. Trận đầu tiên gặp Ba Lan vào ngày 8 tháng 6 năm 2008, Klose không trực tiếp ghi bàn nhưng cả hai bàn thắng của Lukas Podolski đều có dấu ấn của Klose. Hai trận còn lại của vòng bảng gặp Croatia và Áo anh cũng không ghi bàn.

Tại vòng tứ kết ngày 19 tháng 6 gặp Bồ Đào Nha, Klose ghi bàn nâng tỉ số trận đấu lên 2-0 ở phút 26 từ pha đá phạt của Bastian Schweinsteiger. Chung cuộc Đức thắng Bồ Đào Nha 3-2.[26]

Tại vòng bán kết gặp Thổ Nhĩ Kỳ, bàn thắng của Klose ở phút 79 giúp Đức có được lợi thế dẫn bàn 2-1 và người chuyền bóng cho anh ghi bàn là Philipp Lahm. Tuy nhiên bàn bàn thắng này của anh cũng nhờ pha ra vào không hợp lý của thủ môn Rüştü Reçber bên phía Thổ Nhĩ Kỳ. Chung cuộc Đức thắng 3-2 và lọt vào chung kết.[27]

Tại trận chung kết Euro 2008, trận chung kết giải đấu lớn thứ hai của Klose sau trận chung kết World Cup 2002 gặp Brasil, Đức lại một lần nữa thất bại và lần này là trước Tây Ban Nha. Bàn thắng duy nhất trong trận đấu của Fernando Torres ở phút 33 khiến Klose và các đồng đội bỏ lỡ cơ hội có được danh hiệu vô địch Euro lần đầu tiên. Anh còn bị thay ra ở cuối hiệp 2 để nhường chỗ cho tiền đạo Mario Gómez.

World Cup 2010

Klose là một trong 23 cầu thủ Đức tham dự Giải bóng đá vô địch thế giới 2010 và đây là kì World Cup lần thứ ba trong sự nghiệp của anh.[28] Ngay trong trận mở màn thắng Úc 4-0, Klose đã nâng tỉ số trận đấu lên 2-0 bằng quả đánh đầu từ đường chuyền của Philipp Lahm.[29] Tuy nhiên, ở trận đấu tiếp theo với Serbia, anh bị truất quyền thi đấu ở phút thứ 37 của trận đấu vì nhận hai thẻ vàng. Không quá một phút sau khi Klose rời sân, tiền vệ Serbia Milan Jovanovic đã ghi bàn thắng duy nhất của trận đấu.[30]

Đến ngày 27 tháng 6, trong trận đấu tại vòng 2 với đội tuyển Anh, Klose đã ghi bàn thắng mở tỉ số với pha thoát xuống rồi xỉa bóng vào góc lưới từ pha phát bóng dài của thủ môn Đức Manuel Neuer.[31] Trận đấu tứ kết với Argentina là trận đấu thứ 100 của Klose cho đội tuyển quốc gia.[32] Anh đã ghi hai bàn thắng trong trận này giúp Đức giành chiến thắng chung cuộc 4-0, đồng thời có được 14 bàn thắng qua 3 kỳ World Cup để đứng thứ hai trong danh sách các cầu thủ ghi nhiều bàn nhất tại World Cup, bằng với số bàn thắng của Gerd Müller và cách kỷ lục của tiền đạo Brasil Ronaldo 1 bàn.[33]

Trong trận bán kết với Tây Ban Nha, đội tuyển Đức đã để thua 1-0 và Klose cũng đã dính chấn thương khá nặng sau trận đấu này. Do đó, anh đã không thể góp mặt trong trận tranh huy chương đồng với Uruguay để có thể phá vỡ kỷ lục ghi bàn của Ronaldo.[34]

Euro 2012

Ngày 3 tháng 9 năm 2010, Klose ghi bàn thắng duy nhất trong trận đấu mở màn của đội tuyển Đức tại vòng loại Euro 2012 với Bỉ.[35] Trước trận Đức - Azerbaijan ở Köln ngày 7 tháng 9, anh đã được Hiệp hội bóng đá Đức trao tặng kỷ niệm chương nhân dịp anh gia nhập Câu lạc bộ 100, bao gồm những cầu thủ đã khoác áo tuyển Đức từ 100 trận trở lên.[36] Trong trận đấu này, Klose đã lập cú đúp trong chiến thắng 6-1 của đội tuyển Đức.[37] Kết thúc vòng loại Euro 2012, anh ghi được chín bàn thắng và đứng đầu danh sách ghi bàn của đội tuyển Đức trong vòng loại này.[38]

Tại Euro 2012, anh chỉ ghi được duy nhất một bàn thắng trong trận tứ kết thắng Hy Lạp 4-2.[39]

World Cup 2014

Tại vòng loại World Cup 2014, Klose đã đóng góp bốn bàn thắng trên tổng số 36 bàn thắng của đội tuyển nước này.[40] Ngày 7 tháng 6 năm 2014, trong trận giao hữu trước thềm World Cup 2014 giữa Đức và Armenia (kết thúc với tỉ số 6-1), Klose được huấn luyện viên Joachim Löw tung vào sân ở phút 71. Và chỉ 5 phút sau khi có mặt trên sân, Klose đã làm tung lưới Armenia với pha đánh đầu cận thành sau quả tạt bên cánh trái của Lukas Podolski, nâng tỉ số lên thành 3-1. Đây là bàn thắng thứ 69 của Klose sau 132 trận khoác áo đội tuyển Đức và với bàn thắng này, Klose đã chính thức vượt qua Gerd Müller (ghi 68 bàn trong giai đoạn 1967 - 1974) để trở thành cầu thủ ghi nhiều bàn thắng nhất trong lịch sử đội tuyển Đức.[41][42]  

Klose được chọn vào đội hình đội tuyển Đức tham dự World Cup 2014, kỳ World Cup thứ tư trong sự nghiệp của anh, ở tuổi 35.[43] Trong trận đấu vòng bảng với Ghana, khi chỉ mới vào sân được hai phút từ băng ghế dự bị, anh đã ghi bàn thắng gỡ hòa 2-2 cho đội tuyển Đức.[44] Bàn thắng này đã giúp Klose được ghi danh vào lịch sử World Cup với tư cách cầu thủ ghi nhiều bàn thắng nhất trong lịch sử các kỳ World Cup với 15 bàn thắng, bằng với thành tích của Ronaldo.[45]

Tại trận bán kết gặp chính chủ nhà Brasil, Klose đã ghi bàn nâng tỷ số lên 2-0 bằng cú đá bồi cận thành đánh bại thủ thành Júlio César, góp vào chiến thắng đậm lịch sử 7-1 trước đội chủ nhà, qua đó độc chiếm danh hiệu cầu thủ ghi nhiều bàn thắng nhất trong lịch sử các vòng chung kết World Cup với 16 bàn thắng.[46]

Trận đấu cuối cùng của Klose tại các kỳ World Cup là trận chung kết World Cup 2014 với Argentina. Anh được đá chính từ đầu và bị thay ra ở phút 88 để nhường chỗ cho Mario Götze, cầu thủ sau đó đã ghi bàn thắng duy nhất của trận đấu để giúp đội tuyển Đức có danh hiệu vô địch World Cup lần thứ tư trong lịch sử, đồng thời Đức trở thành đội tuyển châu Âu đầu tiên vô địch World Cup trên đất châu Mỹ.[47]

Ngày 11 tháng 8 năm 2014, Klose chính thức giã từ tuyển Đức sau khi cùng đội tuyển Đức giành chức vô địch World Cup 2014, với 136 lần ra sân và ghi được 71 bàn thắng.[6]